/**
  * @file    :adjacency_list_graph.hpp
  * @brief   :邻接链表表示图的模板类
  * @author  :TMJ
  * @version :V1.0.0
  * @date    :2024-01-01
*/

#ifndef GRAPH_ADJACENCY_LIST_GRAPH_H_
#define GRAPH_ADJACENCY_LIST_GRAPH_H_

#include "graph.hpp"
#include <iostream>


// 邻接链表结点定义
template<typename weightType>
struct AdjacencyNode {
    int _adjacencyIndex;             // 邻接点索引
    weightType _weight;              // 边权值
    AdjacencyNode<weightType> *_next;// 下一个邻接点

    // 无参构造函数
    AdjacencyNode() : _adjacencyIndex(-1), _weight(weightType()), _next(nullptr) {}

    // 有参构造函数()
    AdjacencyNode(const int &adjacencyIndex, const weightType &weight,
                  struct AdjacencyNode<weightType> *next = nullptr)
        : _adjacencyIndex(adjacencyIndex), _weight(weight), _next(next) {}

    // 重载 != 运算符
    bool operator!=(const AdjacencyNode<weightType> &adjacencyNode) const {
        return (this->_adjacencyIndex != adjacencyNode._adjacencyIndex ||
                this->_weight != adjacencyNode._weight ||
                this->_next != adjacencyNode._next);
    }

    // 重载 = 运算符
    AdjacencyNode<weightType> &operator=(const AdjacencyNode<weightType> &adjacencyNode) {
        if (this == &adjacencyNode) {
            return *this;
        }
        this->_adjacencyIndex = adjacencyNode._adjacencyIndex;
        this->_weight = adjacencyNode._weight;
        this->_next = adjacencyNode._next;

        return *this;
    }
};

// 邻接链表的头部结构
template<typename vertexType, typename weightType>
struct AdjacencyItem {
    vertexType _data;                 // 顶点数据
    AdjacencyNode<weightType> *_first;// 第一个邻接项

    // 无参构造函数
    AdjacencyItem() : _data(vertexType()), _first(nullptr) {}

    // 清空邻接项
    int clear() {
        int num = 0;
        struct AdjacencyNode<weightType> *del = _first;
        while (del) {
            _first = del->_next;
            delete del;
            del = _first;
            num++;
        }

        _first = nullptr;
        return num;
    }
};

template<typename vertexTy, typename TWeight>
class AdjacencyGraph;

// 重载<<
template<typename vertexType, typename weightType>
std::ostream &operator<<(std::ostream &out, AdjacencyGraph<vertexType, weightType> &adjacency_list_graph);

// 邻接表表示图的模板类
template<typename vertexType, typename weightType>
class AdjacencyGraph : public Graph<vertexType, weightType> {

    // 打印图(重载标准输出)
    friend std::ostream &operator<<<>(std::ostream &out, AdjacencyGraph<vertexType, weightType> &graph_adjacency_list);

private:
    struct AdjacencyItem<vertexType, weightType> *_adjacencyList;// 邻接表

public:
    // 构造函数
    explicit AdjacencyGraph(int maxVertexCount,
                            int type = Graph<vertexType, weightType>::UNDIRECTED);

    // 构造函数
    AdjacencyGraph(int maxVertexCount,
                   const std::vector<Edge<vertexType, weightType>> &edges,
                   const std::vector<vertexType> &_vertices,
                   int type = Graph<vertexType, weightType>::UNDIRECTED);

    // 析构函数
    ~AdjacencyGraph();

    // 获取顶点的索引
    virtual int getVertexIndex(const vertexType &vertex) const;

    // 通过索引获取顶点
    virtual bool getVertex(int index, vertexType &vertex) const;

    // 获取边权值
    virtual bool getEdgeWeight(const vertexType &start, const vertexType &end, weightType &weight) const;

    // 通过顶点索引获取权值
    virtual bool getEdgeWeightByIndex(int startIndex, int endIndex, weightType &weight) const;

    // 插入顶点
    virtual bool insertVertex(const vertexType &vertex);

    // 插入边
    virtual bool insertEdge(const vertexType &start, const vertexType &end, const weightType &weight);

    // 删除顶点
    virtual bool removeVertex(const vertexType &vertex);

    // 删除边
    virtual bool removeEdge(const vertexType &start, const vertexType &end);
};

// 构造函数
template<typename vertexType, typename weightType>
AdjacencyGraph<vertexType, weightType>::AdjacencyGraph(int maxVertexCount,
                                                       int type) {
    // 非法性检测
    if (maxVertexCount < 0) {
        throw std::invalid_argument("最大顶点数量参数有误");
    }
    if (type != Graph<vertexType, weightType>::UNDIRECTED &&
        type != Graph<vertexType, weightType>::DIRECTED) {
        throw std::invalid_argument("图的类型参数有误");
    }

    this->_type = type;
    this->_vertexCount = 0;
    this->_edgeCount = 0;
    this->_maxVertexCount = maxVertexCount;

    // 分别处理有向图和无向图
    if (this->_type == Graph<vertexType, weightType>::UNDIRECTED) {
        this->_degree = new std::vector<int>(this->_maxVertexCount, 0);
        this->_outDegree = nullptr;
        this->_inDegree = nullptr;
    } else {
        this->_degree = nullptr;
        this->_outDegree = new std::vector<int>(this->_maxVertexCount, 0);
        this->_inDegree = new std::vector<int>(this->_maxVertexCount, 0);
    }

    // 分配邻接表的内存空间
    this->_adjacencyList = new AdjacencyItem<vertexType, weightType>[this->_maxVertexCount];
    if (!this->_adjacencyList) {
        throw std::bad_alloc();
    }
}

// 构造函数
template<typename vertexType, typename weightType>
AdjacencyGraph<vertexType, weightType>::AdjacencyGraph(int maxVertexCount,
                                                       const std::vector<Edge<vertexType, weightType>> &edges,
                                                       const std::vector<vertexType> &_vertices,
                                                       int type) {
    // 非法性检测
    if (maxVertexCount < (int) _vertices.size()) {
        throw std::length_error("顶点集合长度过长");
    }
    if (maxVertexCount <= 0) {
        throw std::invalid_argument("最大顶点数量非法");
    }
    if (type != Graph<vertexType, weightType>::UNDIRECTED &&
        type != Graph<vertexType, weightType>::DIRECTED) {
        throw std::invalid_argument("图类型非法");
    }

    this->_type = type;
    this->_vertexCount = 0;
    this->_edgeCount = 0;
    this->_maxVertexCount = maxVertexCount;

    // 分配邻接表空间
    this->_adjacencyList = new AdjacencyItem<vertexType, weightType>[this->_maxVertexCount];
    if (!this->_adjacencyList) {
        throw std::bad_alloc();
    }

    // 插入点
    for (int i = 0; i < (int) _vertices.size(); i++) {
        this->insertVertex(_vertices[i]);
    }

    // 分别处理有向图和无向图
    if (this->_type == Graph<vertexType, weightType>::UNDIRECTED) {
        this->_degree = new std::vector<int>(this->_maxVertexCount, 0);
        this->_inDegree = nullptr;
        this->_outDegree = nullptr;

        for (auto it = edges.begin(); it != edges.end(); it++) {
            this->insertEdge(it->_start, it->_end, it->_weight);// 插入边
            this->insertEdge(it->_end, it->_start, it->_weight);// 插入边
        }
    } else {
        this->_degree = nullptr;
        this->_inDegree = new std::vector<int>(this->_maxVertexCount, 0);
        this->_outDegree = new std::vector<int>(this->_maxVertexCount, 0);

        for (auto it = edges.begin(); it != edges.end(); it++) {
            this->insertEdge(it->_start, it->_end, it->_weight);// 插入边
        }
    }
}

// 析构函数
template<typename vertexType, typename weightType>
AdjacencyGraph<vertexType, weightType>::~AdjacencyGraph() {
    for (int i = 0; i < this->_vertexCount; i++) {
        this->_adjacencyList[i].clear();
    }

    delete[] this->_adjacencyList;
}

// 获取顶点的索引
template<typename vertexType, typename weightType>
int AdjacencyGraph<vertexType, weightType>::getVertexIndex(const vertexType &vertex) const {
    for (int i = 0; i < this->_vertexCount; i++) {
        if (this->_adjacencyList[i]._data == vertex) {
            return i;
        }
    }

    return -1;
}

// 通过索引获取顶点
template<typename vertexType, typename weightType>
bool AdjacencyGraph<vertexType, weightType>::getVertex(int index, vertexType &vertex) const {
    // 非法检测
    if (index < 0 || index >= this->_vertexCount) {
        return false;
    }

    vertex = this->_adjacencyList[index]._data;
    return true;
}

// 获取边的权值
template<typename vertexType, typename weightType>
bool AdjacencyGraph<vertexType, weightType>::getEdgeWeight(const vertexType &start,
                                                           const vertexType &end,
                                                           weightType &weight) const {
    int startIndex = getVertexIndex(start);
    int endIndex = getVertexIndex(end);

    // 非法性检测
    if (startIndex < 0 || startIndex >= this->_vertexCount ||
        endIndex < 0 || endIndex >= this->_vertexCount ||
        startIndex == endIndex) {
        return false;
    }

    AdjacencyNode<weightType> *cur = this->_adjacencyList[startIndex]._first;
    while (cur) {
        if (cur->_adjacencyIndex == endIndex) {
            weight = cur->_weight;
            return true;
        }
        cur = cur->_next;
    }

    return false;
}

// 通过索引获取边权值
template<typename vertexType, typename weightType>
bool AdjacencyGraph<vertexType, weightType>::getEdgeWeightByIndex(int startIndex,
                                                                  int endIndex,
                                                                  weightType &weight) const {
    // 非法检测
    if (startIndex < 0 || startIndex >= this->_vertexCount ||
        endIndex < 0 || endIndex >= this->_vertexCount ||
        startIndex == endIndex) {
        return false;
    }

    AdjacencyNode<weightType> *cur = this->_adjacencyList[startIndex]._first;
    while (cur) {
        if (cur->_adjacencyIndex == endIndex) {
            weight = cur->_weight;
            return true;
        }
        cur = cur->_next;
    }

    return false;
}

// 插入顶点
template<typename vertexType, typename weightType>
bool AdjacencyGraph<vertexType, weightType>::insertVertex(const vertexType &vertex) {
    // 非法性检测
    if (getVertexIndex(vertex) != -1 || this->_vertexCount == this->_maxVertexCount) {
        return false;
    }

    this->_adjacencyList[this->_vertexCount]._data = vertex;
    this->_adjacencyList[this->_vertexCount]._first = nullptr;
    this->_vertexCount++;

    return true;
}

// 插入边
template<typename vertexType, typename weightType>
bool AdjacencyGraph<vertexType, weightType>::insertEdge(const vertexType &start,
                                                        const vertexType &end,
                                                        const weightType &weight) {
    int startIndex = getVertexIndex(start);
    int endIndex = getVertexIndex(end);

    // 非法检测
    // 顶点不合法
    if (startIndex < 0 || startIndex >= this->_vertexCount ||
        endIndex < 0 || endIndex >= this->_vertexCount ||
        startIndex == endIndex) {
        return false;
    }
    // 边不合法
    auto *move = this->_adjacencyList[startIndex]._first;
    while (move) {
        if (move->_adjacencyIndex == endIndex) {
            return false;
        }
        move = move->_next;
    }

    // 找到最后一个边
    auto *cur = this->_adjacencyList[startIndex]._first;
    if (cur != nullptr) {
        while (cur->_next)
            cur = cur->_next;
        cur->_next = new AdjacencyNode<weightType>(endIndex, weight);
    } else {
        this->_adjacencyList[startIndex]._first = new AdjacencyNode<weightType>(endIndex, weight);
    }

    this->_edgeCount++;

    // 分别处理无向图和有向图
    if (this->_type == Graph<vertexType, weightType>::UNDIRECTED) {
        cur = this->_adjacencyList[endIndex]._first;
        if (cur != nullptr) {
            while (cur->_next)
                cur = cur->_next;
            cur->_next = new AdjacencyNode<weightType>(startIndex, weight);
        } else {
            this->_adjacencyList[endIndex]._first = new AdjacencyNode<weightType>(startIndex, weight);
        }
        (*this->_degree)[startIndex]++;
        (*this->_degree)[endIndex]++;
    } else {
        (*this->_inDegree)[endIndex]++;
        (*this->_outDegree)[startIndex]++;
    }

    return true;
}

// 删除顶点
template<typename vertexType, typename weightType>
bool AdjacencyGraph<vertexType, weightType>::removeVertex(const vertexType &vertex) {
    int targetIndex = getVertexIndex(vertex);
    // 非法性检测
    if (targetIndex == -1) {
        return false;
    }

    // 遍历整个邻接表，删除与该顶点有关的所有结点，并处理有向图和无向图
    for (int i = 0; i < this->_vertexCount; ++i) {
        if (i == targetIndex) {
            auto *cur = _adjacencyList[targetIndex]._first;
            while (cur) {
                if (this->_type == Graph<vertexType, weightType>::UNDIRECTED) {
                    (*this->_degree)[cur->_adjacencyIndex]--;
                    (*this->_degree)[targetIndex]--;
                } else {
                    (*this->_inDegree)[cur->_adjacencyIndex]--;
                    (*this->_outDegree)[targetIndex]--;
                }
                cur = cur->_next;
            }
            int delNum = this->_adjacencyList[targetIndex].clear();
            this->_edgeCount -= delNum;
        } else {
            auto *pre = this->_adjacencyList[i]._first;
            if (pre && pre->_adjacencyIndex == targetIndex) {
                this->_adjacencyList[i]._first = pre->_next;
                delete pre;
            } else {
                while (pre && pre->_next) {
                    if (pre->_next->_adjacencyIndex == targetIndex) {
                        auto *cur = pre->_next;
                        pre->_next = cur->_next;
                        delete cur;
                        this->_edgeCount--;

                        if (this->_type == Graph<vertexType, weightType>::UNDIRECTED) {
                            (*this->_degree)[i]--;
                            (*this->_degree)[targetIndex]--;
                        } else {
                            (*this->_inDegree)[targetIndex]--;
                            (*this->_outDegree)[i]--;
                        }
                    }
                    pre = pre->_next;
                }
            }
        }
    }

    return true;
}

// 删除边
template<typename vertexType, typename weightType>
bool AdjacencyGraph<vertexType, weightType>::removeEdge(const vertexType &start, const vertexType &end) {
    int startIndex = getVertexIndex(start);
    int endIndex = getVertexIndex(end);

    // 非法性检测
    if (startIndex < 0 || startIndex >= this->_vertexCount ||
        endIndex < 0 || endIndex >= this->_vertexCount ||
        startIndex == endIndex) {
        return false;
    }

    // 分别处理有向图和无向图
    if (this->_type == Graph<vertexType, weightType>::UNDIRECTED) {
        auto *pre = this->_adjacencyList[startIndex]._first;
        if (pre->_adjacencyIndex == endIndex) {
            this->_adjacencyList[startIndex]._first = pre->_next;
            delete pre;
        } else {
            while (pre->_next) {
                if (pre->_next->_adjacencyIndex == endIndex) {
                    auto *cur = pre->_next;
                    pre->_next = cur->_next;
                    delete cur;
                    break;
                }
                pre = pre->_next;
            }
        }
        pre = this->_adjacencyList[endIndex]._first;
        if (pre->_adjacencyIndex == startIndex) {
            this->_adjacencyList[endIndex]._first = pre->_next;
            delete pre;
        } else {
            while (pre->_next) {
                if (pre->_next->_adjacencyIndex == startIndex) {
                    auto *cur = pre->_next;
                    pre->_next = cur->_next;
                    delete cur;
                    break;
                }
                pre = pre->_next;
            }
        }
        (*this->_degree)[startIndex]--;
        (*this->_degree)[endIndex]--;
    } else {
        auto *pre = this->_adjacencyList[startIndex]._first;
        if (pre->_adjacencyIndex == endIndex) {
            this->_adjacencyList[startIndex]._first = pre->_next;
            delete pre;
        } else {
            while (pre->_next) {
                if (pre->_next->_adjacencyIndex == endIndex) {
                    auto *cur = pre->_next;
                    pre->_next = cur->_next;
                    delete cur;
                    break;
                }
                pre = pre->_next;
            }
        }
        (*this->_inDegree)[endIndex]--;
        (*this->_outDegree)[startIndex]--;
    }

    this->_edgeCount--;

    return true;
}

/*!
 * @brief **输出(打印)图**
 * @tparam TVertex 结点类型模板参数
 * @tparam TWeight 边权值类型模板参数
 * @param out 输出流
 * @param adjacency_list_graph 邻接表图
 * @return 输出流
 * @note
 * 输出(打印)图
 * ----------
 * ----------
 *
 * ----------
 * + **1 打印基本信息**\n\n
 * **1.1 打印结点信息**\n
 * &emsp; 打印文本\n
 * &emsp; **for loop** 遍历结点索引 :\n
 * &emsp;&emsp; 获取当前结点\n
 * &emsp;&emsp; 打印当前结点\n\n
 * **1.2 打印边信息**\n
 * &emsp; 打印文本\n
 * &emsp; **for loop** 遍历边索引 :\n
 * &emsp;&emsp; 获取当前边\n
 * &emsp;&emsp; 打印当前边\n\n
 * + **2 打印邻接表信息**\n\n
 * **for loop** 遍历结点索引 :\n
 * &emsp; 声明cur_vertex(当前索引i对应的结点)\n
 * &emsp; 获取i<b>(当前索引)</b>对应的结点cur_vertex\n\n
 * &emsp; 打印一条文本\n\n
 * &emsp; 声明遍历指针cur_vertex_adjacency, 指向结点cur_vertex的首个邻接项\n
 * &emsp; **while loop** cur_vertex_adjacency不为NULL :\n
 * &emsp;&emsp; 打印当前邻接项的终点\n
 * &emsp;&emsp; **if** 当前邻接项的next不为NULL(不是最后一项) :\n
 * &emsp;&emsp;&emsp; 打印"--->"\n
 * &emsp;&emsp; cur_vertex_adjacency指向next\n
 *
 *
 * ----------
 */
template<typename vertexType, typename weightType>
std::ostream &operator<<(std::ostream &out, AdjacencyGraph<vertexType, weightType> &adjacency_list_graph) {

    // ---------- 1 打印基本信息 ----------

    // ----- 1.1 打印结点信息 -----
    out << "# 基本信息 #" << std::endl;
    out << "结点数量: " << adjacency_list_graph._vertexCount << std::endl;
    out << "边数量：" << adjacency_list_graph._edgeCount << std::endl;
    for (int i = 0; i < adjacency_list_graph._vertexCount; i++) {
        vertexType cur_vertex;
        adjacency_list_graph.getVertex(i, cur_vertex);
        out << cur_vertex << " ";
    }
    out << std::endl;

    // ---------- 2 打印邻接表信息 ----------

    out << "# 邻接表信息 #" << std::endl;

    for (int i = 0; i < adjacency_list_graph._vertexCount; i++) {
        vertexType cur_vertex;
        adjacency_list_graph.getVertex(i, cur_vertex);
        out << cur_vertex << "的邻接结点: ";

        AdjacencyNode<weightType> *cur_vertex_adjacency = adjacency_list_graph._adjacencyList[i]._first;
        while (cur_vertex_adjacency) {
            out << adjacency_list_graph._adjacencyList[cur_vertex_adjacency->_adjacencyIndex]._data;
            if (cur_vertex_adjacency->_next) {
                out << "-->";
            }
            cur_vertex_adjacency = cur_vertex_adjacency->_next;
        }

        out << std::endl;
    }

    return out;
}


#endif// GRAPH_ADJACENCY_LIST_GRAPH_H_
